package algorithm.niuke;

class 解数独 {
    int[][] map = new int[9][9];
    int[] row = new int[9];
    int[] col = new int[9];
    int[][] matrix3 = new int[3][3];
    int hasPut = 0;
    boolean log = true;
    public void solveSudoku(char[][] board) {
        transfer(board);
        find();
        transferBack(board);
    }
    void find(){
        int ti = 0;
        int tj = 0;
        int minPut = 9;
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                int temp = findPutNum(i,j);
                if(temp>0&&minPut>temp){
                    ti = i;
                    tj = j;
                    minPut = temp; 
                }
            }
        }
        for(int k=1;k<=9;k++){
            if(isValid(ti,tj,k)){
                put(ti,tj,k);
                find();
                if(hasPut==81){
                    return;
                }
                remove(ti,tj,k);
            }
        }
    }
    int findPutNum(int i,int j){//找到格子能够存放的数字数量
        int count = 0;
        for(int k=1;k<=9;k++){
            if(isValid(i,j,k)){
                    count++;
            }
        }
        return count;
    }  
    void transfer(char[][] board){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]>='1'&&board[i][j]<='9'){
                    int num = board[i][j] - '0';
                    int tag = 1<<num;
                    row[i] = row[i]|tag;
                    col[j] = col[j]|tag;
                    matrix3[i/3][j/3] = matrix3[i/3][j/3]|tag;
                    map[i][j] = num;
                    hasPut++;
                }
            }
        }
    }
    void transferBack(char[][] board){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                board[i][j] = (char)(map[i][j]+'0');
            }
        }
    }
    
    boolean isValid(int i,int j,int num){
        if(map[i][j]!=0){
            return false;
        }
        int tag = 1<<num;
        if((row[i]&tag)!=0||(col[j]&tag)!=0||(matrix3[i/3][j/3]&tag)!=0){
            return false;
        }
        return true;
    }
    void put(int i,int j,int num){
        int tag = 1<<num;
        row[i] = row[i]|tag;
        col[j] = col[j]|tag;
        matrix3[i/3][j/3] = matrix3[i/3][j/3]|tag;
        map[i][j] = num;
        hasPut++;
    }
    void remove(int i,int j,int num){
        int tag = 1<<num;
        row[i] = row[i]^tag;
        col[j] = col[j]^tag;
        matrix3[i/3][j/3] = matrix3[i/3][j/3]^tag;
        map[i][j] = 0;
        hasPut--;
    }
    
    public static void main(String[] args) {
        String[] str = {"250001000",
                        "300000090",
                        "700600500",
                        "000000081",
                        "000040007",
                        "000005920",
                        "000107000",
                        "800000703",
                        "400009000"};
        char[][] input = new char[9][9];
        for(int i=0;i<9;i++) {
            input[i] = str[i].toCharArray();
        }
        解数独 run = new 解数独();
        run.solveSudoku(input);
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                System.out.print(input[i][j]+" ");
            }
            System.out.println();
        }
    }
}
